package algorithm;

import java.util.Arrays;

public class Dijkstra {
    /**
     * dijkstra算法
     * @param graph 邻接矩阵
     * @param n 顶点数量
     * @param source 起点
     * @return dist数组
     */
    private static int[] dijkstra(int[][] graph, int n, int source) {
        boolean[] visited = new boolean[n];
        // dist数组
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        // 起点
        dist[source] = 0;
        for(int i = 0; i < n; i++) {
            int x = -1;
            // 找到最小距离的下标加入已遍历集合
            for(int y = 0; y < n; y++) {
                if(!visited[y] && (x == -1 || dist[y] < dist[x])) {
                    x = y;
                }
            }

            visited[x] = true;
            // 加入点之后更新到最小值 x -> y
            for(int y = 0; y < n; y++) {
                dist[y] = Math.min(dist[y], dist[y] + graph[x][y]);
            }
        }

        return dist;
    }

    public static void main(String[] args) {

    }
}
